#include"Sort.h"

void InsertSort(int* a, int n)
{
    //i的最大下标为n-2,
    for(int i=0;i<n-1;i++)
    {
        //下标为end+1的元素是每次循环需要排序的元素
    	int end=i;
    	int tmp=a[end+1];
    	while(end>=0)
    	{
        	if(tmp<a[end])
        	{
            	a[end+1]=a[end];
            	--end;
        	}
        	else
        	{
            	break;
        	}
    	}
    	a[end+1]=tmp;
    }
}



void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; ++j)
	{
		int exchange = 0;
		// 单趟
		for (int i = 1; i < n-j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				exchange = 1;
				Swap(&a[i - 1], &a[i]);
			}
		}

		if (exchange == 0)
		{
			break;
		}
	}
}

void ShellSort(int*a,int n)
{
    int gap=n;
    while(gap>1)
    {
        gap=gap/3+1;
        //多组同时进行预排序
        for(int i=0;i<n-gap;i++)
        {
            int end=i;
            int tmp=a[end+gap];
            while(end>=0)
            {
                if(tmp<a[end])
                {
                    a[end+gap]=a[end];
                    end-=gap;
                }
                else
                {
                    break;
                }
            }
            a[end+gap]=tmp;
        }
    }
}


void SelectSort(int*a,int n)
{
    int left=0,right=n-1;
    while(left<right)
    {
        int mini=left,maxi=left;
        for(int i=left+1;i<=right;i++)
        {
            if(a[i]<a[mini]) mini=i;
            if(a[i]>a[maxi]) maxi=i;
        }
        Swap(&a[mini],&a[left]);
        if(maxi==left)
        {
            maxi=mini;
        }
        Swap(&a[maxi],&a[right]);
        left++;
        right--;
    }
}

void HeapSort(int*a,int n)
{
    //先建堆,从最后一个元素的parent开始，最后一层的结点本来就是堆，所以不用进行排序
    
    //建立大堆
    for(int i=(n-1-1)/2;i>=0;i--)
    {
        //向下调整
       AdjustDown(a,n,i);
    }
    size_t end=n-1;
    while(end>0)
    {
        Swap(&a[0],&a[end]);
        AdjustDown(a,end,0);
        end--;
    }
}


void QuickSort(int*a,int begin,int end)
{
    if(begin>=end)
        	return ;
    //返回中间的值
    if(end-begin+1<=13)
    {
        InsertSort(a+begin,end-begin+1);
    }
    else
    {
        int key=PartSort3(a,begin,end);
    	QuickSort(a,0,key-1);
    	QuickSort(a,key+1,end-1);   
    }
}



void MergeSortNonR(int* a, int n)
{
    int*tmp=(int*)malloc(sizeof(int)*n);
    assert(tmp);
    _MergeSortNonR(a,0,n-1,tmp);
    free(tmp);
}

void CounSort(int*a,int n)
{
    int max=a[0],min=a[0];
    for(int i=0;i<n;i++)
    {
        if(a[i]>max)
            max=a[i];
        if(a[i]<min)
            min=a[i];
    }
    //找到数据的范围
    int range=max-min+1;
    int*res=(int*)malloc(sizeof(int)*range);
    memset(res,0,sizeof(res));
    for(int i=0;i<n;i++)
    {
       //计数器
        res[a[i]-min]++;
    }
    int index=0;
    for(int i=0;i<range;i++)
    {
        while(res[i]--)
        {
            a[index++]=i+min;
        }
    }
}